package array.binarySearch;

/**
 * 题目:给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
       如果数组中不存在目标值 target，返回 [-1, -1]。
       你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

 * 思路：分别寻找到左边界和右边界，因此有两个函数：searchleft和searchRight
 * 注意: 设置leftborder=-2，rightborder=-2，表示没有找到目标值，
 *       不可以设置为-1，因为-1数组中存在目标值，为最开始
 *
 * 确定好：计算出来的右边界是不包含target的右边界，左边界同理。
 */

public class findFirstLastPosition{
    public int[] searchRange(int[] nums, int target) {
        int leftborder=searchleft(nums,target);
        int rightborder=searchRight(nums,target);

        // 情况一:target 在数组范围的右边或者左边
        if (leftborder == -2 || rightborder == -2) {
            return new int[] {-1,-1};}
        // 情况三:target 在数组范围中，且数组中存在target
        if (rightborder - leftborder > 1) {
            return new int []{leftborder + 1, rightborder - 1};}
        // 情况二:target 在数组范围中，且数组中不存在target
        return new int []{-1, -1};

    }
    public int searchleft(int[] nums,int target) {
        int right=nums.length-1;
        int left=0;
        int leftborder=-2;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]<target){
                left=mid+1;
            }
            else{
                right=mid-1;
                leftborder=right;

            }
        }
        return leftborder;
    }

    public int searchRight(int []nums,int target){
        int left =0;
        int right = nums.length-1;
        int rightBorder = -2;
        while(left<=right){
            int mid=(left+right)/2;
            if(nums[mid]>target){
                right=mid-1;
            }
            else{
                left=mid+1;
                rightBorder=left;
            }

        }
        return rightBorder;
    }
}